package org.flint.data.structure.bst;

import com.google.common.base.Preconditions;

import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

/**
 * @author flint92
 */
public class BinarySearchTree<E extends Comparable<E>> {

    /**
     * 内部节点类
     */
    class Node {
        E val;
        Node left;
        Node right;

        Node(E val) {
            this.val = val;
        }
    }

    private Node root;

    private int size;

    public int size() {
        return this.size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 添加元素
     *
     * @param e     元素
     */
    public void add(E e) {
        Preconditions.checkNotNull(e);
        root = addReverse(root, e);
    }

    /**
     * 递归实现向root为根的BST添加元素
     *
     * @param root  根
     * @param e     被添加的元素
     * @return      插入新节点后BST的根
     */
    private Node addReverse(Node root, E e) {
        if (Objects.isNull(root)) {
            size++;
            return new Node(e);
        }

        int c = e.compareTo(root.val);
        if (c > 0) {
            root.right = addReverse(root.right, e);
        } else {
            root.left = addReverse(root.left, e);
        }

        return root;
    }


    /**
     * 判断是否包含元素
     *
     * @param e         元素
     * @return          bool
     */
    public boolean contains(E e) {
        return containsReverse(root, e);
    }

    private boolean containsReverse(Node root, E e) {
        if (Objects.isNull(root)) {
            return false;
        }
        int c = e.compareTo(root.val);
        if (c == 0) {
            return true;
        } else if (c < 0) {
            return containsReverse(root.left, e);
        } else {
            return containsReverse(root.right, e);
        }
    }

    /**
     * 前序遍历
     */
    public void preOrder() {
        preOrder(root);
    }

    private void preOrder(Node root) {
        if (Objects.isNull(root)) {
            return;
        }
        // 先访问root节点
        System.out.println(root.val);
        // 再访问左子树
        preOrder(root.left);
        // 最后访问右子树
        preOrder(root.right);
    }

    /**
     * 中序遍历
     */
    public void inOrder() {
        inOrder(root);
    }

    private void inOrder(Node root) {
        if (Objects.isNull(root)) {
            return;
        }
        // 先访问左子树
        inOrder(root.left);
        // 再访问该root节点
        System.out.println(root.val);
        // 最后访问右子树
        inOrder(root.right);
    }

    /**
     * 后序遍历
     */
    public void postOrder() {
        postOrder(root);
    }

    private void postOrder(Node root) {
        if (Objects.isNull(root)) {
            return;
        }
        // 先访问左子树
        postOrder(root.left);
        // 再访问右子树
        postOrder(root.right);
        // 最后访问该root节点
        System.out.println(root.val);
    }

    /**
     * 层序遍历
     */
    public void levelOrder() {
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            Node curr = queue.remove();
            System.out.println(curr.val);

            if (curr.left != null) {
                queue.add(curr.left);
            }
            if (curr.right != null) {
                queue.add(curr.right);
            }
        }
    }

    /**
     * 返回BST的最小元素
     * @return      最小元素值
     */
    public E findMin() {
        if (size == 0) {
            throw new IllegalArgumentException("bst is empty");
        }
        return findMin(root).val;
    }

    private Node findMin(Node root) {
        Node curr = root;
        while (curr.left != null) {
            curr = curr.left;
        }
        return curr;
    }

    /**
     * 返回BST的最大元素
     * @return      最大元素值
     */
    public E findMax() {
        if (size == 0) {
            throw new IllegalArgumentException("bst is empty");
        }
        return findMax(root).val;
    }

    private Node findMax(Node root) {
        Node curr = root;
        while (curr.right != null) {
            curr = curr.right;
        }
        return curr;
    }


    /**
     * 删除最小元素
     * @return  被删除的元素
     */
    public E removeMin() {
        E e = findMin();
        root = removeMin(root);
        return e;
    }

    private Node removeMin(Node root) {
        if (Objects.isNull(root.left)) {
            Node right = root.right;
            root.right = null;
            size--;
            return right;
        }
        root.left =  removeMin(root.left);
        return root;
    }

    /**
     * 删除最大元素
     * @return  被删除的元素
     */
    public E removeMax() {
        E e = findMax();
        root = removeMax(root);
        return e;
    }

    private Node removeMax(Node root) {
        if (Objects.isNull(root.right)) {
            Node left = root.left;
            root.left = null;
            size--;
            return left;
        }
        root.right =  removeMin(root.right);
        return root;
    }

    public void remove(E e) {
        root = remove(root, e);
    }

    private Node remove(Node root, E e) {
        Preconditions.checkNotNull(e);
        if (Objects.isNull(root)) {
            return null;
        }
        int c = e.compareTo(root.val);
        if (c < 0) {
            root.left = remove(root.left, e);
        } else if (c > 0){
            root.right = remove(root.right, e);
        } else {
            // 待删除节点左子树为空
            if (Objects.isNull(root.left)) {
                Node right = root.right;
                root.right = null;
                size--;
                return right;
            }
            // 待删除节点右子树为空
            if (Objects.isNull(root.right)) {
                Node left = root.left;
                root.left = null;
                size--;
                return left;
            }
            // 待删除节点左右子树都存在
            Node right = root.right;
            // 找右子树的最小节点替换root或找左子树的最大节点替换root 下面考虑第一种情况
            // 1、先找出右自己中的最小节点
            Node successor = findMin(right);
            // 2、删除右子树中的最小节点 并将删除之后的右子树设为被删除最小节点的右子树
            // caution: removeMin方法里面就执行了size-1操作
            successor.right = removeMin(right);
            // 3、将原来的左子树设为被删除最小节点的左子树
            successor.left = root.left;
            // 至此 successor就替换掉了root
            // 4、删除root节点
            root.left = root.right = null;
            // 5、返回successor
            return successor;
        }
        return root;
    }

    public static void main(String[] args) {
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        int[] nums = {5, 3, 6, 8, 4, 2};

        for (int num : nums) {
            bst.add(num);
        }

        //////////////////////////////
        //            5             //
        //          ↙  ↘           //
        //         3     6          //
        //       ↙  ↘    ↘        //
        //      2    4      8       //
        //////////////////////////////

        bst.preOrder();

        System.out.println("===================================");

        // 中序遍历天然的排序
        bst.inOrder();

        System.out.println("===================================");

        // 后序遍历的一个典型应用就是内存释放
        bst.postOrder();

        System.out.println("===================================");

        bst.levelOrder();

        System.out.println("===================================");

        System.out.println(bst.findMin());

        System.out.println("===================================");

        System.out.println(bst.findMax());
    }

}
